// https://leetcode.cn/problems/distant-barcodes/description/

// 算法思路总结：
// 1. 贪心策略解决相邻不重复排列问题
// 2. 统计频率并找到出现次数最多的数字
// 3. 先间隔放置最高频数字避免冲突
// 4. 剩余数字按序填充空位位置
// 5. 时间复杂度：O(n)，空间复杂度：O(n)

#include <iostream>
using namespace std;

#include <vector>
#include <string>
#include <algorithm>

class Solution 
{
public:
    vector<int> rearrangeBarcodes(vector<int>& barcodes) 
    {
        int m = barcodes.size();
        int maxVal = 0, maxCount = 0;
        unordered_map<int, int> hash;

        for (const int& num : barcodes)
        {
            if (maxCount < ++hash[num])
            {
                maxCount = hash[num];
                maxVal = num;
            }
        }

        vector<int> ret(m);
        int index = 0;
        for (int i = 0 ; i < maxCount ; i++)
        {
            ret[index] = maxVal;
            index += 2;
        }

        hash.erase(maxVal);
        for (auto& [x, y] : hash)
        {
            for (int i = 0 ; i < y ; i++)
            {
                if (index >= m)
                {
                    index = 1;
                }
                ret[index] = x;
                index += 2;
            }
        }

        return ret;
    }
};

int main()
{
    vector<int> barcodes1 = {1,1,1,2,2,2};
    vector<int> barcodes2 = {1,1,1,1,2,2,3,3};

    Solution sol;

    auto v1 = sol.rearrangeBarcodes(barcodes1);
    auto v2 = sol.rearrangeBarcodes(barcodes2);

    for (const int& num : v1) 
        cout << num << " ";
    cout << endl;

    for (const int& num : v2) 
        cout << num << " ";
    cout << endl;    

    return 0;
}